
/**
 * 第k个排列
 * 题目描述

给定参数 n，从 1 到 n 会有 n 个整数：1,2,3,…,n，这 n 个数字共有 n! 种排列。

按大小顺序升序列出所有排列的情况，并一一标记，当 n = 3 时，所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

输入描述
输入两行：

第一行为 n，给定 n 的范围是 [1，9]
第二行为 k，给定 k 的范围是 [1，n!]
输出描述
输出排在第 k 位置的数字。

用例
输入	
3
3
输出	213
说明	3的排列有123,132,213…,那么第三位置就是213
输入	
2
2
输出	21
说明	2的排列有12,21，那么第二位置的为21。

 */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
  * 
  题目解析
本题最简单的思路是使用回溯算法求解所有全排列，然后取出第 k 个排列。

关于全排列求解，可以参考：

但是求解全排列的时间复杂度很高。

这里我提供一种更优解题思路：

假设 n = 3，那么有全排列如下：

123，132，213，231，312，321
我们可以发现，以 1 开头的排列有两个，以 2 开头的排列有两个，以 3 开头的排列有两个。

其实原理很简单，以 1 开头的排列，剩余部分由2，3组成，可以形成 (n-1)! 个排列，即以 1 开头的排列有 (n-1)! 个。
即我们可以认为 n = 3 时，每 (n-1)! 个排列一组，同组的排列开头数字是相同的。

为了方便理解，我们将 k 转化为 索引，即 第 k 个排列，其实是索引 k-1 的排列。

比如下面全排列集合中第 3 个排列 "213"，其实是索引 2 的排列

123，132，213，231，312，321
我们通过 k--，将 k 变为索引。

现在要求索引 k 的排列，那么索引 k 的排列处于哪一组呢？

k / (n-1)!
比如 n = 3，（索引）k = 2时，k / (n-1)! == 1，即处于下面 索引1组 中

123，132，213，231，312，321
那么具体是该组哪一个呢？

k % (n-1)!
比如 n = 3，（索引）k=2时，k % (n-1)! == 0，即处于下面 索引1组 中 索引0的排列

123，132，213，231，312，321
以上就是解法的大体思路，那么该如何实现呢？

我们需要 n = 3，nums = [1, 2, 3] 组成的全排列集合中，找到（索引） k = 2的排列

首先，（索引）k = 2 的排列的第一个元素的索引

k / (n-1)! == 1
即第一个元素为 nums[1]。之后更新 k = k % (n-1)!。

接下来，我们要在 n = 2，nums = [1, 3] 组成的全排列集合中，找到（索引）k = 0 的排列的第一个元素的索引

k / (n-1)! == 1
即第一个元素为 nums[0]。之后更新 k = k % (n-1)!。

接下来，我们要在 n = 1，nums = [3] 组成的全排列中，找到（索引）k=0 的排列的第一个元素的索引

k / (n-1)! == 1
即第一个元素为 nums[0]。

之后 n = 0，结束查找。

上面实现过程中，我们通过不断地分解问题规模，将大问题变为相同性质的小问题。这里可以使用递归，也可以不用递归。下面源码实现中使用的是非递归解法。

  */
public class 第k个排列 {
    
    public static void main(String[] args) {

        try{

            Scanner sc = new Scanner(System.in);
 
            int n = sc.nextInt();
            int k = sc.nextInt();
    
            List<Integer> nums = new ArrayList<>(); // 记录1~n
            int fact = 1; // 初始为 n!
    
            for (int i = 1; i <= n; i++) {
                nums.add(i);
                fact *= i;
            }
    
            StringBuilder sb = new StringBuilder(); // 记录结果
    
            k--; // 将 k 变为索引，比如第1个数，其实就是索引0的数
    
            for (int i = n; i > 0; i--) {
                fact /= i;  // 一共 i 个数, 每 fact 个一组
                sb.append(nums.remove(k / fact)); // k/fact 表示索引k的数位于哪一组
                k %= fact; // k%fact 表示索引k的数位于 k/fact组 的第几位
            }
    
            System.out.println(sb);

        }catch(Exception e){

            e.printStackTrace();
        }
    }
}
